package demo.practice.backtrack;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

public class P17 {
    Map<Character, String> keys = Map.of('2', "abc", '3', "def", '4', "ghi", '5', "jkl", '6', "mno", '7',
            "pqrs", '8', "tuv", '9', "wxyz");


    public static void main(String[] args) {
        P17 p17=new P17();
        p17.letterCombinations("234");
    }

    public List<String> letterCombinations(String digits) {


        List<String> list= new ArrayList<>();
        back(list,digits);
        return list;
    }

    private void back( List<String> list,String digits){

        if(digits==null|| digits.length()==0) {
            return;
        }

        List<String> list_new= new ArrayList<>();

        char c = digits.charAt(0);
        String s = keys.get(c);
        if(list.size()==0){
            for(char e :s.toCharArray()){
                list.add(String.valueOf(e));
            }
        }else{
            for(char e :s.toCharArray()){
               for(String o:list){
                   list_new.add(o.concat(String.valueOf(e)) );
               }
            }

            list.clear();
            list.addAll(list_new);
        }

        back(list,digits.substring(1));

    }

}
